// ECE556 - Copyright 2013 University of Wisconsin-Madison.  All Rights Reserved.

#include "ece556.h"
//#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <cassert>
#include <math.h>
#include <time.h>

extern int eval_mode;
extern long cnt_unrouted;

using namespace std;


ofstream &operator<<(ofstream& stream, int data){
        stringstream ss;
        ss << data;
        stream << ss.str();
        return stream;
}


ostream &operator<<(ostream& os, point pnt){
        os << '(' << pnt.x << ',' << pnt.y << ')';
        return os;
}


static inline int get2DEdgeID(const point p1, const point p2, routingInst *rst){
  	
  	// horizontal edge
	if (p1.y == p2.y)
	{
		if (p2.x - p1.x == 1)
			return p1.y * (rst->gx - 1) + p1.x ;
		else if (p1.x - p2.x == 1)
			return p1.y * (rst->gx - 1) + p2.x ;
		else
		{
			// error, do nothing	
		}
	}
	else if (p1.x == p2.x)
	{
		if (p2.y - p1.y == 1)
			return rst->gy * (rst->gx - 1) + p1.x * (rst->gy - 1) + p1.y ;
		else if (p1.y - p2.y == 1)
			return rst->gy * (rst->gx - 1) + p1.x * (rst->gy - 1) + p2.y ;
		else
		{
			// error, do nothing	
		}
	}
	else
	{
		// error, do nothing
	}
        
	fprintf (stderr, "can't get edge :");
        cout << p1 << "\t" << p2 << endl;
	return -1;
  	
}

  
static inline int getPoints2D(int edgeID, point &p1, point &p2, routingInst *rst){
  
        // horizontal edge
        if (edgeID < rst->gy * (rst->gx - 1))
        {
                p1.x = edgeID % (rst->gx - 1);
                p1.y = (edgeID - p1.x) / (rst->gx - 1);
                p2.x = p1.x + 1;
                p2.y = p1.y;
                
                return 0;
        }
        //vertical edge
        else
        {
                int base = rst->gy * (rst->gx - 1);
		
                p1.y = (edgeID - base) % (rst->gy - 1);
                p1.x = (edgeID - base - p1.y) / (rst->gy - 1);
                p2.x = p1.x;
                p2.y = p1.y + 1;
                
                return 0;
        }
        
        return 1;
}


int readBenchmark(const char *fileName, routingInst *rst){
        
        ifstream fin;
        fin.open(fileName);
        if(!fin)
        {
                cout<<"Fail to open input file"<<endl;
                return 0;
        }
        
        cout << "Parsing benchmark...." << endl;
        char *temp = new char[1024];
        
        int i, j;
        int tmp_x, tmp_y; // for pins

        // line 1
        fin >> temp; // "grid"
        fin >> (rst->gx) >> rst->gy;
        rst->numEdges = (rst->gx -1)*rst->gy + (rst->gy -1)*rst->gx; // edge number
        
        int capacity;
        fin >> temp >> capacity;
        rst->cap = capacity;
        
        fin >> temp >> temp >> rst->numNets; // num net #
        rst->nets = new net[rst->numNets]; 
	
        for(i = 0; i < rst->numNets; i++) // each net
        {
                stringstream ss;
                ss << i;
                
                rst->nets[i].id = i; // nets
                fin >> temp >> rst->nets[i].numPins; // numPins
                
		rst->nets[i].pins = new point[rst->nets[i].numPins];
                for(j = 0; j < rst->nets[i].numPins; j++) // each pin
                {
                        fin >> tmp_x >> tmp_y; // pins
                        rst->nets[i].pins[j].x = tmp_x;
                        rst->nets[i].pins[j].y = tmp_y;
                } // each pin
        } // each net
        
        rst->edgeCaps = new int[rst->numEdges];
        rst->edgeUtils = new int[rst->numEdges];
        rst->edgeHistory = new double[rst->numEdges];
        memset(rst->edgeHistory, 1.0, sizeof(int) * rst->numEdges);
        
        // initialize with default edge capacity before adjustment
        for(i = 0; i < rst->numEdges; i++)
                rst->edgeCaps[i] = capacity;
        
        int N_adjust;
        fin >> N_adjust; // adjusted numEdges
        
        point p1, p2;
        for(i = 0; i < N_adjust; i++) // adjustments
        {
                fin >> p1.x >> p1.y >> p2.x >> p2.y;
                int block_cap;
                fin >> block_cap;
                int edge_id = get2DEdgeID(p1, p2, rst);
                rst->edgeCaps[edge_id] = block_cap;
        }
        
        fin.close();
        delete [] temp;
        return 1;
}


int checkPntInseg(point &p1, point &p2, const point &mid){
        if(mid == p1 || mid == p2){
                //cout << "impossible!" << endl;
        }
        else{
                if(p1.x == mid.x && p1.x == p2.x){
                        if(mid.y <= max(p1.y, p2.y) && mid.y >= min(p1.y, p2.y))
                                return 1;
                }
                
                if(p1.y == mid.y && p1.y == p2.y){
                        if(mid.x <= max(p1.x, p2.x) && mid.x >= min(p1.x, p2.x))
                                return 1;
                }
        }
                
        return 0;
}


int quickEvalWLOF(routingInst *rst){
        
        int i, j, k;
        long tot_wl = 0;
        long tot_of = 0;
        
        for(i = 0; i < rst->numEdges; i++)
                rst->edgeUtils[i] = rst->edgeCaps[i];
        
        for(i = 0; i < rst->numNets; i++) // each net
        {
                set<int> edges;
                set<int>::iterator it_set;
                for(j = 0; j < rst->nets[i].numCRoutes; j++) // here correct
                {
                        for(k = 0; k < rst->nets[i].croutes[j].numSegs; k++){
                                
                                point p1, p2;
                                p1.x = rst->nets[i].croutes[j].segments[k].p1.x;
                                p1.y = rst->nets[i].croutes[j].segments[k].p1.y;
                        
                                p2.x = rst->nets[i].croutes[j].segments[k].p2.x;
                                p2.y = rst->nets[i].croutes[j].segments[k].p2.y;
                                
                                if(p1.x != p2.x && p1.y != p2.y){
                                        cout << "net has non-straight segments!" << endl;
                                        exit(0);                
                                }
                        
                                if(p1.x == p2.x && p1.y == p2.y)
                                        continue;
                                
                                if(p1.x == p2.x){
                                        point p1_, p2_;
                                        p1_.x = p1.x;
                                        p2_.x = p2.x;
                                        if(max(p1.y, p2.y) - min(p1.y, p2.y) == 1){
                                                p1_.y = min(p1.y, p2.y);
                                                p2_.y = max(p1.y, p2.y);
                                                int edge_id = get2DEdgeID(p1_, p2_, rst);
                                                edges.insert(edge_id);
                                        }
                                        else{
                                                for(i = min(p1.y, p2.y); i < max(p1.y, p2.y); i++){
                                                        p1_.y = i;
                                                        p2_.y = i + 1;
                                                        int edge_id = get2DEdgeID(p1_, p2_, rst);
                                                        edges.insert(edge_id);
                                                }
                                        }
                                }
                                else{
                                        point p1_, p2_;
                                        p1_.y = p1.y;
                                        p2_.y = p2.y;
                                        if(max(p1.x, p2.x) - min(p1.x, p2.x) == 1){
                                                p1_.x = min(p1.x, p2.x);
                                                p2_.x = max(p1.x, p2.x);
                                                int edge_id = get2DEdgeID(p1_, p2_, rst);
                                                edges.insert(edge_id);
                                        }
                                        else{
                                                for(i = min(p1.x, p2.x); i < max(p1.x, p2.x); i++){
                                                        p1_.x = i;
                                                        p2_.x = i + 1;
                                                        int edge_id = get2DEdgeID(p1_, p2_, rst);
                                                        edges.insert(edge_id);
                                                }
                                        }
                                }
                        }
                }
                
                tot_wl += edges.size();
                for(it_set = edges.begin(); it_set != edges.end(); it_set++)
                        rst->edgeUtils[*it_set]--;
        }
        
        for(i = 0; i < rst->numEdges; i++){
                if(rst->edgeUtils[i] < 0)
                        tot_of += abs(rst->edgeUtils[i]);
        }
        
        cout << "total wirelength is " << tot_wl << endl;
        cout << "total overflow is " << tot_of << endl;
        
        return 1;
}


int evalSolution(const char *fileName, routingInst *rst){
        
        int i, j, k;
        ifstream fin;
        fin.open(fileName);
        if(!fin)
        {
                cout<<"Fail to open input file"<<endl;
                return 0;
        }
        
        cout << "Reading solution..." << endl;
        
        char line_content[256];
        long tot_wl = 0;
        long tot_of = 0;
        long net_cnt = 0;
        long line_number = 0;
        
        set<int> nets;
        while(!fin.eof()){
                
                fin.getline(line_content, 256);
                string netName = line_content;
                line_number++;
                
                if(netName[0] != 'n'){
                        cout << "Error: In line " << line_number << ", ";
                        cout << "net name " << netName << " is invalid!" << endl;
                        exit (0);
                }
                
                int net_id = atoi(netName.substr(1).c_str());
                nets.insert(net_id);
                
                set<int> edges;
                set<int>::iterator it_set;
                vector<pair<point, point> > Segs;
                while(1){
                        
                        unsigned int p1_x, p1_y, p2_x, p2_y;
                        fin.getline(line_content, 256);
                        string tmp = line_content;
                        line_number++;
                        if(tmp == "!")
                                break;
                        
                        //starting node position
                        int pos1 = tmp.find('(');
                        int pos2 = tmp.find(',', pos1 + 1);
                        stringstream ss;
                        ss << tmp.substr(pos1 + 1, pos2 - 1 - pos1 - 1 + 1);
                        ss << ' ';
                        
                        pos1 = tmp.find(')', pos2 + 1);
                        ss << tmp.substr(pos2 + 1, pos1 - 1 - pos2 - 1 + 1);
                        
                        if(!(ss >> p1_x >> p1_y)){
                                cout << "Error: net " << netName << " has invalid segment coordinates!" << endl;
                                exit(0);
                        }
                        //cout << "Starting node index (" << p1_x << "," << p1_y << ")" << endl;
                        
                        //ending node position
                        stringstream ss1;
                        pos2 = tmp.find(',', pos1 + 3);
                        ss1 << tmp.substr(pos1 + 3, pos2 - 1 - pos1 - 3 + 1);
                        ss1 << ' ';
                        
                        pos1 = tmp.find(')', pos2 + 1);
                        ss1 << tmp.substr(pos2 + 1, pos1 - 1 - pos2 - 1 + 1);
                        
                        if(!(ss1 >> p2_x >> p2_y)){
                                cout << "Error: net " << netName << " has invalid segment coordinates!" << endl;
                                exit(0);
                        }
                        //cout << "Ending node index (" << p2_x << "," << p2_y << ")" << endl;
                        
                        if(p1_x > rst->gx || p1_y > rst->gy || p2_x > rst->gx || p2_y > rst->gy){
                                cout << "Error: net " << netName << " has invalid segment coordinates!" << endl;
                                exit(0);
                        }
                        
                        point p1, p2;
                        p1.x = p1_x;
                        p1.y = p1_y;
                        
                        p2.x = p2_x;
                        p2.y = p2_y;
                        
                        if(p1.x != p2.x && p1.y != p2.y){
                                cout << "Error: net " << netName << " has non-straight segments!" << endl;
                                exit(0);                
                        }
                        
                        if(p1.x == p2.x && p1.y == p2.y)
                                continue;
                        
                        for(i = 0; i < Segs.size(); i++)
                                if(Segs[i].first == p1 && Segs[i].second == p2)
                                        break;
                        
                        if(i == Segs.size())
                                Segs.push_back(make_pair(p1, p2));
                        
                        if(p1.x == p2.x){
                                point p1_, p2_;
                                p1_.x = p1.x;
                                p2_.x = p2.x;
                                if(max(p1.y, p2.y) - min(p1.y, p2.y) == 1){
                                        p1_.y = min(p1.y, p2.y);
                                        p2_.y = max(p1.y, p2.y);
                                        int edge_id = get2DEdgeID(p1_, p2_, rst);
                                        edges.insert(edge_id);
                                }
                                else{
                                        for(i = min(p1.y, p2.y); i < max(p1.y, p2.y); i++){
                                                p1_.y = i;
                                                p2_.y = i + 1;
                                                int edge_id = get2DEdgeID(p1_, p2_, rst);
                                                edges.insert(edge_id);
                                        }
                                }
                        }
                        else{
                                point p1_, p2_;
                                p1_.y = p1.y;
                                p2_.y = p2.y;
                                if(max(p1.x, p2.x) - min(p1.x, p2.x) == 1){
                                        p1_.x = min(p1.x, p2.x);
                                        p2_.x = max(p1.x, p2.x);
                                        int edge_id = get2DEdgeID(p1_, p2_, rst);
                                        edges.insert(edge_id);
                                }
                                else{
                                        for(i = min(p1.x, p2.x); i < max(p1.x, p2.x); i++){
                                                p1_.x = i;
                                                p2_.x = i + 1;
                                                int edge_id = get2DEdgeID(p1_, p2_, rst);
                                                edges.insert(edge_id);
                                        }
                                }
                        }
                }
                
                tot_wl += edges.size();
                for(it_set = edges.begin(); it_set != edges.end(); it_set++)
                        rst->edgeCaps[*it_set]--;
                
                if(eval_mode == 0){
                        map<point, int> myMap;
                        map<point, int>::iterator it_map;
                        for(i = 0; i < Segs.size(); i++){
                                if(myMap.find(Segs[i].first) == myMap.end())
                                        myMap[Segs[i].first] = 1;
                                else
                                        myMap[Segs[i].first]++;
                        
                                if(myMap.find(Segs[i].second) == myMap.end())
                                        myMap[Segs[i].second] = 1;
                                else
                                        myMap[Segs[i].second]++;
                        }
                
                        vector<point> unsolvedPins;
                        for(i = 0; i < rst->nets[net_id].numPins; i++){
                                for(it_map = myMap.begin(); it_map != myMap.end(); it_map++)
                                        if((*it_map).first == rst->nets[net_id].pins[i])
                                                break;
                                if(it_map == myMap.end())
                                        unsolvedPins.push_back(rst->nets[net_id].pins[i]);
                        }
                        
                        map<point, vector<point> > graph;
                        vector<point> redundant_point;
                        //single appearance node
                        for(it_map = myMap.begin(); it_map != myMap.end(); it_map++){
                                if((*it_map).second == 1){
                                        for(i = 0; i < rst->nets[net_id].numPins; i++)
                                                if((*it_map).first == rst->nets[net_id].pins[i])
                                                        break;
                                        if(i == rst->nets[net_id].numPins){
                                                for(j = 0; j < Segs.size(); j++){
                                                        if(checkPntInseg(Segs[j].first, Segs[j].second, (*it_map).first) == 1){
                                                                for(k = 0; k < graph[(*it_map).first].size() && graph[(*it_map).first][k] != Segs[j].first; k++);
                                                                if(k == graph[(*it_map).first].size())
                                                                        graph[(*it_map).first].push_back(Segs[j].first);
                                                        
                                                                for(k = 0; k < graph[(*it_map).first].size() && graph[(*it_map).first][k] != Segs[j].second; k++);
                                                                if(k == graph[(*it_map).first].size())
                                                                        graph[(*it_map).first].push_back(Segs[j].second);
                                                                
                                                                break;
                                                        }
                                                }
                                                if(j == Segs.size()){
                                                        redundant_point.push_back((*it_map).first);
                                                        //cout << "Warning: the segment starts from or ends at point (" << (*it_map).first.x
                                                        //<< "," << (*it_map).first.y << ") in net " << netName << "  is redundant!" << endl;
                                                        //exit(0);
                                                }
                                        }
                                }
                        }
                
                        //no appearance pins
                        for(i = 0; i < unsolvedPins.size(); i++){
                                for(j = 0; j < Segs.size(); j++){
                                        if(checkPntInseg(Segs[j].first, Segs[j].second, unsolvedPins[i]) == 1){
                                                for(k = 0; k < graph[unsolvedPins[i]].size() && graph[unsolvedPins[i]][k] != Segs[j].first; k++);
                                                if(k == graph[unsolvedPins[i]].size())
                                                        graph[unsolvedPins[i]].push_back(Segs[j].first);
                                        
                                                for(k = 0; k < graph[unsolvedPins[i]].size() && graph[unsolvedPins[i]][k] != Segs[j].second; k++);
                                                if(k == graph[unsolvedPins[i]].size())
                                                        graph[unsolvedPins[i]].push_back(Segs[j].second);
                                        
                                                break;
                                        }
                                }
                        
                                if(j == Segs.size()){
                                        cout << "Error: net " << netName << " has its pin (" << unsolvedPins[i].x
                                             << "," << unsolvedPins[i].y << ") not connected!" << endl;
                                        exit(0);
                                }
                        }
                
                        //Now there should be no single points, create graph
                        for(i = 0; i < Segs.size(); i++){
                                for(k = 0; k < graph[Segs[i].first].size() && graph[Segs[i].first][k] != Segs[i].second; k++);
                                if(k == graph[Segs[i].first].size())
                                        graph[Segs[i].first].push_back(Segs[i].second);
                        
                                for(k = 0; k < graph[Segs[i].second].size() && graph[Segs[i].second][k] != Segs[i].first; k++);
                                if(k == graph[Segs[i].second].size())
                                        graph[Segs[i].second].push_back(Segs[i].first);        
                        }
                
                        queue<point> myQueue;
                        vector<point> connected_points;
                        myQueue.push(rst->nets[net_id].pins[0]);
                        connected_points.push_back(rst->nets[net_id].pins[0]);
                        while(!myQueue.empty()){
                                for(i = 0; i < graph[myQueue.front()].size(); i++){
                                        for(j = 0; j < connected_points.size(); j++)
                                                if(connected_points[j] == graph[myQueue.front()][i])
                                                        break;
                                        if(j == connected_points.size()){
                                                connected_points.push_back(graph[myQueue.front()][i]);
                                                myQueue.push(graph[myQueue.front()][i]);
                                        }
                                } 
                          
                                myQueue.pop();
                        }
                        
                        for(i = 1; i < rst->nets[net_id].numPins; i++){
                                for(j = 0; j < connected_points.size(); j++)
                                        if(connected_points[j] == rst->nets[net_id].pins[i])
                                                break;
                                if(j == connected_points.size()){
                                        cout << "Error: net " << netName << " is not fully connected!" << endl;
                                        exit(0);
                                }
                        }
                        
                        for(i = 0; i < redundant_point.size(); i++)
                                cout << "Warning: the segment starting from or ending at point " << redundant_point[i] << " in net " << netName << " is redundant!" << endl;
                }
                
                net_cnt++;
                if(net_cnt == rst->numNets)
                        break;
        }
        
        if(nets.size() != rst->numNets){
                cout << "Error: Your solution has overlooked at least one net!" << endl;
                exit(0);
        }
        cout << "All nets connected!" << endl;
        
        for(i = 0; i < rst->numEdges; i++){
                if(rst->edgeCaps[i] < 0)
                        tot_of += abs(rst->edgeCaps[i]);
        }
        
        cout << "total wirelength is " << tot_wl << endl;
        cout << "total overflow is " << tot_of << endl;
        
        return 1;
}


unsigned int computeDistance(point &p1, point& p2){
        return (abs(p1.x - p2.x) + abs(p1.y - p2.y));
}


int pinOrdering(routingInst *rst){
        
        int i, j, k;
        cout << "Executing pin ordering..." << endl;
        for(i = 0; i < rst->numNets; i++)
        {
                multimap<unsigned int, pair<point, point> > myMap;
                multimap<unsigned int, pair<point, point> >::iterator it_map, it_map1, it_map2;
                for(j = 0; j < rst->nets[i].numPins; j++)
                {
                        for(k = j + 1; k < rst->nets[i].numPins; k++){
                                unsigned int distance = computeDistance(rst->nets[i].pins[j], rst->nets[i].pins[k]);
                                myMap.insert(make_pair(distance, make_pair(rst->nets[i].pins[j], rst->nets[i].pins[k])));
                        }
                }
                
                vector<point> newPins;
                it_map = myMap.begin();
                newPins.push_back((*it_map).second.first);
                newPins.push_back((*it_map).second.second);
                
                while(newPins.size() < rst->nets[i].numPins){
                        
                        point beg_pnt, end_pnt;
                        beg_pnt = newPins.front();
                        end_pnt = newPins.back();
                        
                        for(it_map = myMap.begin(); it_map != myMap.end(); it_map++){
                                if(((*it_map).second.first == beg_pnt && (*it_map).second.second == end_pnt)
                                   || ((*it_map).second.first == end_pnt && (*it_map).second.second == beg_pnt)){
                                        myMap.erase(it_map);
                                        break;
                                }
                        }
                        
                        multimap<unsigned int, pair<point, point> > myMap1, myMap2;
                        for(it_map = myMap.begin(); it_map != myMap.end(); it_map++){
                                if((*it_map).second.first == beg_pnt || (*it_map).second.second == beg_pnt)
                                        myMap1.insert(*it_map);
                        }
                        
                        for(it_map = myMap.begin(); it_map != myMap.end(); it_map++){
                                if((*it_map).second.first == end_pnt || (*it_map).second.second == end_pnt)
                                        myMap2.insert(*it_map);
                        }
                        
                        it_map1 = myMap1.begin();
                        it_map2 = myMap2.begin();
                        
                        int cond;
                        point pick_pnt;
                        if((*it_map1).first < (*it_map2).first){
                                pick_pnt = (beg_pnt == (*it_map1).second.second) ? (*it_map1).second.first : (*it_map1).second.second;
                                cond = 0;
                        }
                        else{
                                pick_pnt = (end_pnt == (*it_map2).second.second) ? (*it_map2).second.first : (*it_map2).second.second;
                                cond = 1;
                        }
                        
                        if(cond == 0){
                                for(it_map = myMap.begin(); it_map != myMap.end(); ){
                                        if((*it_map).second.first == beg_pnt || (*it_map).second.second == beg_pnt){
                                                myMap.erase(it_map++);
                                        }
                                        else
                                                ++it_map;
                                }
                                newPins.insert(newPins.begin(), pick_pnt);
                        }
                        else{
                                for(it_map = myMap.begin(); it_map != myMap.end(); ){
                                        if((*it_map).second.first == end_pnt || (*it_map).second.second == end_pnt){
                                                myMap.erase(it_map++);
                                        }
                                        else
                                                ++it_map;
                                }
                                newPins.insert(newPins.end(), pick_pnt);
                        }        
                }
        }
        
        return 1;
}


int pinOrderingMST(routingInst *rst){
        
        cout << "Using FLUTE to generate MST for init pin ordering..." << endl;
        int i, j;
        /*
        ofstream out("mst_source");
        for(i = 0; i < rst->numNets; i++)
        {
                if(rst->nets[i].numPins <= 2)
                        continue;
                
                out << rst->nets[i].id << " " << rst->nets[i].numPins << endl;
                for(j = 0; j < rst->nets[i].numPins; j++)
                {
                        out << rst->nets[i].pins[j].x << " ";
                        out << rst->nets[i].pins[j].y << endl;
                }
        }
        
        pid_t pid=fork();
        if (pid==0) {
                char *argv[]={"",NULL};
                execv("./flute-ece556", argv);
                exit(127);
        }
        return 1;
        */
        //read-in solutions
        ifstream fin("mst_out");
        char line[80];
        while(!fin.eof()){
                if(fin.getline(line, 80) == NULL)
                        break;
                
                int net_id;
                net_id = atoi(line);
                //rst->nets[net_id].mst.clear();
                while(1){
                        fin.getline(line, 80);
                        if(!strcmp(line, "!"))
                                break;
                        
                        point p1, p2;
                        sscanf(line, "%d%d%d%d", &p1.x, &p1.y, &p2.x, &p2.y);
                        rst->nets[net_id].mst.push_back(make_pair(p1, p2));
                }
        }
        
        for(i = 0; i < rst->numNets; i++)
        {
                if(rst->nets[i].numPins == 2)
                        rst->nets[i].mst.push_back(make_pair(rst->nets[i].pins[0], rst->nets[i].pins[1]));
        }
        
        cout << "MST generation done!" << endl;
        return 1;
}


void shortest_path(point &beg_pnt, point &end_pnt, set<int>& temp_set, routingInst *rst){
        
        int i;
        point mid1, mid2, p1, p2;
        
        set<int>::iterator it_set;
        set<int> temp_set1, temp_set2;
        
        mid1.x = beg_pnt.x;
        mid1.y = end_pnt.y;
        
        mid2.x = end_pnt.x;
        mid2.y = beg_pnt.y;
        
        //first L-shape route
        p1.x = mid1.x; p2.x = mid1.x;
        for(i = min(beg_pnt.y, mid1.y); i < max(beg_pnt.y, mid1.y); i++){
                p1.y = i;
                p2.y = i + 1;
                int edge_id = get2DEdgeID(p1, p2, rst);
                temp_set1.insert(edge_id);
        }
        
        p1.y = mid1.y; p2.y = mid1.y;
        for(i = min(end_pnt.x, mid1.x); i < max(end_pnt.x, mid1.x); i++){
                p1.x = i;
                p2.x = i + 1;
                int edge_id = get2DEdgeID(p1, p2, rst);
                temp_set1.insert(edge_id);
        }
        
        
        //second L-shape route
        p1.x = mid2.x; p2.x = mid2.x;
        for(i = min(end_pnt.y, mid2.y); i < max(end_pnt.y, mid2.y); i++){
                p1.y = i;
                p2.y = i + 1;
                int edge_id = get2DEdgeID(p1, p2, rst);
                temp_set2.insert(edge_id);
        }
        
        p1.y = mid2.y; p2.y = mid2.y;
        for(i = min(beg_pnt.x, mid2.x); i < max(beg_pnt.x, mid2.x); i++){
                p1.x = i;
                p2.x = i + 1;
                int edge_id = get2DEdgeID(p1, p2, rst);
                temp_set2.insert(edge_id);
        }
        
        int tot_vio1 = 0;
        for(it_set = temp_set1.begin(); it_set != temp_set1.end(); it_set++)
                tot_vio1 += (rst->edgeUtils[*it_set] - 1 >= 0)? 0 : abs(rst->edgeUtils[*it_set] - 1);
        
        int tot_vio2 = 0;
        for(it_set = temp_set2.begin(); it_set != temp_set2.end(); it_set++)
                tot_vio2 += (rst->edgeUtils[*it_set] - 1 >= 0)? 0 : abs(rst->edgeUtils[*it_set] - 1);
        
        if(tot_vio1 < tot_vio2)
                swap(temp_set, temp_set1);
        else
                swap(temp_set, temp_set2);
}


int spSingleNet(int net_id, routingInst *rst){//shortest path for a single net
        
        int i, j;
        point p1, p2;
        set<int>::iterator it_set;
        set<int> temp_set, whole_set;
        for(j = 0; j < rst->nets[net_id].numPins - 1; j++){
                shortest_path(rst->nets[net_id].pins[j], rst->nets[net_id].pins[j+1], temp_set, rst);
                whole_set.insert(temp_set.begin(), temp_set.end());
        }
        
        for(it_set = whole_set.begin(); it_set != whole_set.end(); it_set++)
                rst->edgeUtils[*it_set]--;
        
        rst->nets[net_id].finalRoute.numSegs = whole_set.size();
        rst->nets[net_id].finalRoute.segments = new segment[whole_set.size()];
        it_set = whole_set.begin();
        for(i = 0; i < rst->nets[net_id].finalRoute.numSegs; i++){
                if(getPoints2D(*it_set, p1, p2, rst) == 1)
                        cout << "Can't find edge id " << *it_set << endl;
                rst->nets[net_id].finalRoute.segments[i].p1 = p1;
                rst->nets[net_id].finalRoute.segments[i].p2 = p2;
                it_set++;
        }
        
        swap(rst->nets[net_id].edges, whole_set);
        rst->nets[net_id].routed = true;
        
        return (int)rst->nets[net_id].edges.size();
}


void reconstructPath(point &beg_pnt, point &end_pnt, map<point, pair<point, double> >& pathReconstructMap, set<int>& path, routingInst *rst){
        
        //cout << "Reconstructing path..." << endl;
        point cur_pnt = end_pnt;
        while(cur_pnt != beg_pnt){
                //cout << cur_pnt << endl;
                point temp = pathReconstructMap[cur_pnt].first;
                int edge_id = get2DEdgeID(cur_pnt, temp, rst);
                path.insert(edge_id);
                cur_pnt = temp;
        }        
}


double penaltyCompute(const int edge_id, routingInst *rst){
        int diff = rst->edgeCaps[edge_id] - rst->edgeUtils[edge_id];
        double ratio = (double)diff / rst->edgeCaps[edge_id];
        return (ratio * rst->edgeHistory[edge_id]);
        /*
          if(ratio <= 0.5)
                return 0.0;
        else if(ratio > 0.5 && ratio <= 0.6)
                return 0.1;
        else if(ratio > 0.6 && ratio <= 0.7)
                return 0.25;
        else if(ratio > 0.7 && ratio <= 0.8)
                return 0.4;
        else if(ratio > 0.8 && ratio <= 0.9)
                return 0.55;
        else if(ratio > 0.9 && ratio <= 1.0)
                return 0.7;
        else
                return 1.0;
        */
        /*
        if(ratio <= 0.8)
                return 0.0;
        else if(ratio > 0.8 && ratio <= 0.9)
                return 0.1;
        else if(ratio > 0.9 && ratio <= 1.0)
                return 0.2;
        else
                return 1.0;
        */
        /*
        if(ratio <= 0.3)
                return 0.0;
        else if(ratio > 0.3 && ratio <= 0.4)
                return 0.1;
        else if(ratio > 0.4 && ratio <= 0.5)
                return 0.2;
        else if(ratio > 0.5 && ratio <= 0.6)
                return 0.3;
        else if(ratio > 0.6 && ratio <= 0.7)
                return 0.4;
        else if(ratio > 0.7 && ratio <= 0.8)
                return 0.5;
        else if(ratio > 0.8 && ratio <= 0.9)
                return 0.6;
        else if(ratio > 0.9 && ratio <= 1.0)
                return 0.7;
        else
                return 1.0;
        */
}


static inline bool inBoundingbox(point lleft, const int width, const int length, point pnt){
        //This is for general purpose computation of whether a point is
        //within a rectangle, no matter the rectangle is rotated or not.
        //This is quite easy to be generalized to deal with convex hall.
        //For rectangle, the problem is easier to solve. What we need is
        //only the information of three points, let's say A, B, C, (D) and M.
        //%%%C-------B
        //%%%----M----
        //%%%A-------B
        //we only need to check if 0 < AM(dotproduct)AB < AB(dotproduct)AB
        //(or simply length^2) && 0 < AM(dotproduct)AC < AC(dotproduct)AC (width^2)
        // This problem is even simpler for a rectangle placed paralleled
        //to the X-Axis. 
        //This function needs to be called so frequently that it should be inlined. 
        point vec_pnt, vec_AB, vec_AC;
        vec_pnt.x = (pnt.x - lleft.x);
        vec_pnt.y = (pnt.y - lleft.y);
        
        //vec_AB.x = length;
        //vec_AB.y = 0;
        
        //vec_AC.x = 0;
        //vec_AC.y = width;
        
        if(vec_pnt.x < length && vec_pnt.x > 0 &&
           vec_pnt.y < width && vec_pnt.y > 0) 
                return true;
        else
                return false;
}


int LeeRoutepick(int net_id, double control_factor, routingInst *rst){
        //Note that this net_id is not the real net id
        
        int i, j;
        point beg_pnt, end_pnt;
        //cout << "Routing net " << net_id << endl;
        for(i = 0; i < rst->nets[net_id].numPins - 1; i++){
                beg_pnt = rst->nets[net_id].pins[i];
                end_pnt = rst->nets[net_id].pins[i + 1];
                
                //Create bounding box, first find the llf coordinate
                point llf;
                llf.x = min(beg_pnt.x, end_pnt.x);
                llf.y = min(beg_pnt.y, end_pnt.y);
                
                //Initial bbx
                //int bbx_width, bbx_length;
                //bbx_width = abs(beg_pnt.y - end_pnt.y);
                //bbx_length = abs(beg_pnt.x - end_pnt.x);
                
                //Bfs is OK
                set<point> visited_pnts;
                set<point>::iterator it_vp;
                
                beg_pnt.resetScore();
                queue<point> myQ;
                myQ.push(beg_pnt);
                visited_pnts.insert(beg_pnt);

                int flag = 0;
                while(!myQ.empty()){
                        point cur_pnt = myQ.front();
                        if(cur_pnt == end_pnt){
                                end_pnt = cur_pnt;
                                flag = 1;
                                break;
                        }

                        //At most four possible neighboring nodes
                        point p_w, p_n, p_s, p_e; 
                        p_w.x = max(cur_pnt.x - 1, 0);
                        p_w.y = cur_pnt.y;
                        
                        p_n.x = cur_pnt.x;
                        p_n.y = min(cur_pnt.y + 1, rst->gy - 1);
                        
                        p_e.x = min(cur_pnt.x + 1, rst->gx - 1);
                        p_e.y = cur_pnt.y;
                        
                        p_s.x = cur_pnt.x;
                        p_s.y = max(cur_pnt.y - 1, 0);
                        
                        int overflow = 0;
                        if(p_w != cur_pnt && visited_pnts.find(p_w) == visited_pnts.end()){
                                //double factor = penaltyCompute(edge_id, rst);
                                int edge_id = get2DEdgeID(p_w, cur_pnt, rst);
                                if(rst->edgeUtils[edge_id] < 0)
                                        overflow = abs(rst->edgeUtils[edge_id]);
                                p_w.score = min(p_w.score, cur_pnt.score + overflow + 1); // +edge_weight later
                                visited_pnts.insert(p_w);
                                myQ.push(p_w);
                        }
                        
                        overflow = 0;
                        if(p_n != cur_pnt && visited_pnts.find(p_n) == visited_pnts.end()){
                                int edge_id = get2DEdgeID(p_n, cur_pnt, rst);
                                if(rst->edgeUtils[edge_id] < 0)
                                        overflow = abs(rst->edgeUtils[edge_id]);
                                p_n.score = min(p_n.score, cur_pnt.score + overflow + 1); // +edge_weight later
                                visited_pnts.insert(p_n);
                                myQ.push(p_n);
                        }
                        
                        overflow = 0;
                        if(p_e != cur_pnt && visited_pnts.find(p_e) == visited_pnts.end()){
                                int edge_id = get2DEdgeID(p_e, cur_pnt, rst);
                                if(rst->edgeUtils[edge_id] < 0)
                                        overflow = abs(rst->edgeUtils[edge_id]);
                                p_e.score = min(p_e.score, cur_pnt.score + overflow + 1); // +edge_weight later
                                visited_pnts.insert(p_e);
                                myQ.push(p_e);
                        }
                        
                        overflow = 0;
                        if(p_s != cur_pnt && visited_pnts.find(p_s) == visited_pnts.end()){
                                int edge_id = get2DEdgeID(p_s, cur_pnt, rst);
                                if(rst->edgeUtils[edge_id] < 0)
                                        overflow = abs(rst->edgeUtils[edge_id]);
                                p_s.score = min(p_s.score, cur_pnt.score + overflow + 1); // +edge_weight later
                                visited_pnts.insert(p_s);
                                myQ.push(p_s);
                        }
                        
                        myQ.pop();
                }
                
                if(flag == 0){
                        //Now should enlarge
                        cout << "end_point not found for pin pair "
                             << beg_pnt << " and " << end_pnt << endl;
                        cin.get();
                }
                
                //Backtrack to find the route
                vector<point> route;
                point cur_pnt = end_pnt;
                route.push_back(cur_pnt);
                while(cur_pnt != beg_pnt){
                        //At most four possible neighboring nodes
                        point p_w, p_n, p_s, p_e; 
                        p_w.x = max(cur_pnt.x - 1, 0);
                        p_w.y = cur_pnt.y;
                        
                        p_n.x = cur_pnt.x;
                        p_n.y = min(cur_pnt.y + 1, rst->gy - 1);
                        
                        p_e.x = min(cur_pnt.x + 1, rst->gx - 1);
                        p_e.y = cur_pnt.y;
                        
                        p_s.x = cur_pnt.x;
                        p_s.y = max(cur_pnt.y - 1, 0);
                        
                        point next_pnt;
                        if( p_w != cur_pnt && ( (it_vp = visited_pnts.find(p_w)) != visited_pnts.end() ) ){
                                //Careful, not to use the p_w since it's temp variable
                                if((*it_vp).score < next_pnt.score)
                                        next_pnt = *it_vp;
                        }
                        
                        if( p_e != cur_pnt && ( (it_vp = visited_pnts.find(p_e)) != visited_pnts.end() ) ){
                                if((*it_vp).score < next_pnt.score)
                                        next_pnt = *it_vp;
                        }
                        
                        if( p_n != cur_pnt && ( (it_vp = visited_pnts.find(p_n)) != visited_pnts.end() ) ){
                                if((*it_vp).score < next_pnt.score)
                                        next_pnt = *it_vp;
                        }
                        
                        if( p_s != cur_pnt && ( (it_vp = visited_pnts.find(p_s)) != visited_pnts.end() ) ){
                                if((*it_vp).score < next_pnt.score)
                                        next_pnt = *it_vp;
                        }
                        
                        cur_pnt = next_pnt;
                        route.push_back(cur_pnt);
                }
                
                set<int> route_;
                for(j = 0; j < route.size() - 1; j++){
                        point cur_pnt = route[j + 1];
                        point pre_pnt = route[j];
                        
                        //cout << "previous pnt: " << pre_pnt << ", with score " << pre_pnt.score << endl;
                        //cout << "current pnt: " << cur_pnt << ", with score " << cur_pnt.score << endl;
                        
                        int edge_id = get2DEdgeID(cur_pnt, pre_pnt, rst);
                        route_.insert(edge_id);
                }
                
                //cin.get();
                rst->nets[net_id].edges.insert(route_.begin(), route_.end());
                // In this implementation, no need to clear scores of the
                // points visited in each iteration
        }
        
        if(!rst->nets[net_id].edges.empty()){
                rst->nets[net_id].routed = true;
                rst->nets[net_id].finalRoute.numSegs = rst->nets[net_id].edges.size();
                rst->nets[net_id].finalRoute.segments = new segment[rst->nets[net_id].edges.size()];
                point p1, p2;
                set<int>::iterator it_set = rst->nets[net_id].edges.begin();
                for(i = 0; i < rst->nets[net_id].finalRoute.numSegs; i++){
                        if(getPoints2D(*it_set, p1, p2, rst) == 1)
                                cout << "Can't find edge id " << *it_set << endl;
                        rst->nets[net_id].finalRoute.segments[i].p1 = p1;
                        rst->nets[net_id].finalRoute.segments[i].p2 = p2;
                        rst->edgeUtils[*it_set]--;
                        it_set++;
                }
        }
        
        return 0;
}


int AStarRoutepick(int net_id, double control_factor, routingInst *rst){
        
        int i;
        int tot_wl = 0;
        point beg_pnt, end_pnt;
        
        set<int> edges;
        set<int>::iterator it_set;
        /*Switching between MST and Original pin ordering*/
        //for(i = 0; i < rst->nets[net_id].mst.size(); i++){        
                //beg_pnt = rst->nets[net_id].mst[i].first;
                //end_pnt = rst->nets[net_id].mst[i].second;
        for(i = 0; i < rst->nets[net_id].numPins - 1; i++){
                beg_pnt = rst->nets[net_id].pins[i];
                end_pnt = rst->nets[net_id].pins[i + 1];
                
                vector<pair<double, point> > rankMap;
                vector<pair<double, point> >::iterator it_rankMap, it_rankMap1, it_rankMap2;
                //pathReconstructMap[point] = pre_pnt, g_score
                map<point, pair<point, double> > pathReconstructMap;
                vector<point> closed_set; //visited nodes, can be re-visted
                
                double distance = computeDistance(beg_pnt, end_pnt);
                const double ori_distance = distance;
                
                rankMap.push_back(make_pair(distance, beg_pnt));
                pathReconstructMap[beg_pnt] = make_pair(beg_pnt, 0);
                
                bool routed = false;
                while(!rankMap.empty()){
                        
                        it_rankMap = rankMap.begin();
                        point cur_pnt = (*it_rankMap).second;
                        double cur_f_score = (*it_rankMap).first;
                        
                        //if(cur_f_score >= 1.1 * ori_distance)
                        //break;
                        
                        if(cur_pnt == end_pnt){
                                set<int> temp_set;
                                reconstructPath(beg_pnt, end_pnt, pathReconstructMap, temp_set, rst);
                                for(it_set = temp_set.begin(); it_set != temp_set.end(); it_set++){
                                        if(edges.find(*it_set) == edges.end()){
                                                edges.insert(*it_set);
                                                rst->edgeUtils[*it_set]--;
                                        }
                                }
                                
                                rst->nets[net_id].routed = true;
                                routed = true;
                                break;
                        }
                        
                        //At most four possible neighboring nodes
                        point p_w, p_n, p_s, p_e; 
                        p_w.x = max(cur_pnt.x - 1, 0);
                        p_w.y = cur_pnt.y;
                        
                        p_n.x = cur_pnt.x;
                        p_n.y = min(cur_pnt.y + 1, rst->gy - 1);
                        
                        p_e.x = min(cur_pnt.x + 1, rst->gx -1);
                        p_e.y = cur_pnt.y;
                        
                        p_s.x = cur_pnt.x;
                        p_s.y = max(cur_pnt.y - 1, 0);
                        
                        //set<point> temp;
                        queue<point> neighbors;
                        vector<double> penArray;
                        if(p_w != cur_pnt){
                                int edge_id = get2DEdgeID(cur_pnt, p_w, rst);
                                penArray.push_back(penaltyCompute(edge_id, rst));
                                //penArray.push_back(floor(penaltyCompute(edge_id, rst) * ori_distance));
                                if(rst->edgeUtils[edge_id] > 0)
                                        neighbors.push(p_w);
                        }
                        if(p_n != cur_pnt){
                                int edge_id = get2DEdgeID(cur_pnt, p_n, rst);
                                penArray.push_back(penaltyCompute(edge_id, rst));
                                //penArray.push_back(floor(penaltyCompute(edge_id, rst) * ori_distance));
                                if(rst->edgeUtils[edge_id] > 0)
                                        neighbors.push(p_n);
                        }
                        if(p_e != cur_pnt){
                                int edge_id = get2DEdgeID(cur_pnt, p_e, rst);
                                penArray.push_back(penaltyCompute(edge_id, rst));
                                //penArray.push_back(floor(penaltyCompute(edge_id, rst) * ori_distance));
                                if(rst->edgeUtils[edge_id] > 0)
                                        neighbors.push(p_e);
                        }
                        if(p_s != cur_pnt){
                                int edge_id = get2DEdgeID(cur_pnt, p_s, rst);
                                penArray.push_back(penaltyCompute(edge_id, rst));
                                //penArray.push_back(floor(penaltyCompute(edge_id, rst) * ori_distance));
                                if(rst->edgeUtils[edge_id] > 0)
                                        neighbors.push(p_s);
                        }
                        
                        int j = 0;
                        while(!neighbors.empty()){
                                bool visited = false;
                                double temp_g_score = pathReconstructMap[cur_pnt].second + computeDistance(cur_pnt, neighbors.front()) + penArray[j];
                                if(find(closed_set.begin(), closed_set.end(), neighbors.front()) != closed_set.end()){
                                        if(temp_g_score >= pathReconstructMap[neighbors.front()].second){
                                                neighbors.pop();
                                                continue;
                                        }
                                        visited = true;
                                }
                                
                                bool inRankMap = false;
                                for(it_rankMap1 = rankMap.begin(); it_rankMap1 != rankMap.end(); it_rankMap1++)
                                        if((*it_rankMap1).second == neighbors.front())
                                                break;
                                if(it_rankMap1 != rankMap.end())
                                        inRankMap = true;
                                
                                /*
                                if(inRankMap == true && visited == false && temp_g_score < pathReconstructMap[neighbors.front()].second){
                                        double distance = temp_g_score + computeDistance(neighbors.front(), end_pnt) + penArray[j];
                                        if(distance < (*it_rankMap1).first){
                                                pathReconstructMap[neighbors.front()] = make_pair(cur_pnt, temp_g_score);
                                                rankMap.erase(it_rankMap1);
                                                for(it_rankMap1 = rankMap.begin(); it_rankMap1 != rankMap.end(); it_rankMap1++){
                                                        if(distance <= (*it_rankMap1).first){
                                                                rankMap.insert(it_rankMap1, make_pair(distance, neighbors.front()));
                                                                break;
                                                                }
                                                }
                                        }
                                        
                                        neighbors.pop();
                                        j++;
                                        continue;
                                        }
                                */
                                
                                if(inRankMap == false || visited == false || (visited == true && temp_g_score < pathReconstructMap[neighbors.front()].second))//old one
                                        //if((inRankMap == false && visited == false) || (visited == true && temp_g_score < pathReconstructMap[neighbors.front()].second))
                                        pathReconstructMap[neighbors.front()] = make_pair(cur_pnt, temp_g_score);
                                
                                if(inRankMap == false){
                                        double distance = pathReconstructMap[neighbors.front()].second + computeDistance(neighbors.front(), end_pnt);// + penArray[j];
                                        for(it_rankMap1 = rankMap.begin(); it_rankMap1 != rankMap.end(); it_rankMap1++){
                                                if(distance <= (*it_rankMap1).first){
                                                        rankMap.insert(it_rankMap1, make_pair(distance, neighbors.front()));
                                                        break;
                                                }
                                        }
                                        if(it_rankMap1 == rankMap.end()){
                                                //can also use cur_f_score times control factor!
                                                if(distance <= ori_distance * control_factor)
                                                        rankMap.insert(it_rankMap1, make_pair(distance, neighbors.front()));
                                        }
                                }
                                
                                neighbors.pop();
                                j++;
                        }
                        
                        vector<point>::iterator it_point;
                        for(it_point = closed_set.begin(); it_point != closed_set.end(); it_point++)
                                if(*it_point == cur_pnt)
                                        break;
                        if(it_point == closed_set.end())
                                closed_set.push_back(cur_pnt);
                        
                        for(it_rankMap1 = rankMap.begin(); it_rankMap1 != rankMap.end(); it_rankMap1++){
                                if((*it_rankMap1).second == cur_pnt && cur_f_score == (*it_rankMap1).first){
                                        rankMap.erase(it_rankMap1);
                                        break;
                                }
                        }                        
                }
                
                if(routed == false){
                        for(it_set = edges.begin(); it_set != edges.end(); it_set++)
                                rst->edgeUtils[*it_set]++;
                        edges.clear();
                        
                        rst->nets[net_id].routed = false;
                        cnt_unrouted++;
                        break;
                }
        }
        
        if(!edges.empty()){
                rst->nets[net_id].finalRoute.numSegs = edges.size();
                rst->nets[net_id].finalRoute.segments = new segment[edges.size()];
                point p1, p2;
                it_set = edges.begin();
                for(i = 0; i < rst->nets[net_id].finalRoute.numSegs; i++){
                        if(getPoints2D(*it_set, p1, p2, rst) == 1)
                                cout << "Can't find edge id " << *it_set << endl;
                        rst->nets[net_id].finalRoute.segments[i].p1 = p1;
                        rst->nets[net_id].finalRoute.segments[i].p2 = p2;
                        it_set++;
                }
                
                tot_wl += edges.size();
                swap(rst->nets[net_id].edges, edges);
        }
        
        return tot_wl;
}


int AStarStarRoutepick(int net_id, double control_factor, routingInst *rst){
        
        int i;
        int tot_wl = 0;
        point beg_pnt, end_pnt;
        
        set<int> edges;
        set<int>::iterator it_set;
        for(i = 0; i < rst->nets[net_id].numPins - 1; i++){
                
                beg_pnt = rst->nets[net_id].pins[i];
                end_pnt = rst->nets[net_id].pins[i + 1];
                
                vector<pair<double, point> > rankMap;
                vector<pair<double, point> >::iterator it_rankMap, it_rankMap1;
                //pathReconstructMap[point] = pre_pnt, g_score
                map<point, pair<point, double> > pathReconstructMap;
                vector<point> closed_set; //visited nodes, can be re-visted
                
                double distance = computeDistance(beg_pnt, end_pnt);
                double ori_distance = distance;
                rankMap.push_back(make_pair(distance, beg_pnt));
                pathReconstructMap[beg_pnt] = make_pair(beg_pnt, 0);
                
                bool routed = false;
                while(!rankMap.empty()){
                        
                        it_rankMap = rankMap.begin();
                        point cur_pnt = (*it_rankMap).second;
                        double cur_f_score = (*it_rankMap).first;
                        
                        //if(cur_f_score >= 2 * ori_distance)
                        //break;
                        
                        if(cur_pnt == end_pnt){
                                set<int> temp_set;
                                reconstructPath(beg_pnt, end_pnt, pathReconstructMap, temp_set, rst);
                                for(it_set = temp_set.begin(); it_set != temp_set.end(); it_set++){
                                        if(edges.find(*it_set) == edges.end()){
                                                edges.insert(*it_set);
                                                rst->edgeUtils[*it_set]--;
                                        }
                                }
                                
                                rst->nets[net_id].routed = true;
                                routed = true;
                                break;
                        }
                        
                        //At most four possible neighboring nodes
                        point p_w, p_n, p_s, p_e; 
                        p_w.x = max(cur_pnt.x - 1, 0);
                        p_w.y = cur_pnt.y;
                        
                        p_n.x = cur_pnt.x;
                        p_n.y = min(cur_pnt.y + 1, rst->gy - 1);
                        
                        p_e.x = min(cur_pnt.x + 1, rst->gx -1);
                        p_e.y = cur_pnt.y;
                        
                        p_s.x = cur_pnt.x;
                        p_s.y = max(cur_pnt.y - 1, 0);
                        
                        //set<point> temp;
                        queue<point> neighbors;
                        vector<int> penArray;
                        if(p_w != cur_pnt){
                                int edge_id = get2DEdgeID(cur_pnt, p_w, rst);
                                penArray.push_back(floor(penaltyCompute(edge_id, rst) * ori_distance));
                                if(rst->edgeUtils[edge_id] > 0)
                                        neighbors.push(p_w);
                        }
                        if(p_n != cur_pnt){
                                int edge_id = get2DEdgeID(cur_pnt, p_n, rst);
                                penArray.push_back(floor(penaltyCompute(edge_id, rst) * ori_distance));
                                if(rst->edgeUtils[edge_id] > 0)
                                neighbors.push(p_n);
                        }
                        if(p_e != cur_pnt){
                                int edge_id = get2DEdgeID(cur_pnt, p_e, rst);
                                penArray.push_back(floor(penaltyCompute(edge_id, rst) * ori_distance));
                                if(rst->edgeUtils[edge_id] > 0)
                                neighbors.push(p_e);
                        }
                        if(p_s != cur_pnt){
                                int edge_id = get2DEdgeID(cur_pnt, p_s, rst);
                                penArray.push_back(floor(penaltyCompute(edge_id, rst) * ori_distance));
                                if(rst->edgeUtils[edge_id] > 0)
                                neighbors.push(p_s);
                        }
                        
                        int j = 0;
                        while(!neighbors.empty()){
                                bool visited = false;
                                double temp_g_score = pathReconstructMap[cur_pnt].second + computeDistance(cur_pnt, neighbors.front());
                                if(find(closed_set.begin(), closed_set.end(), neighbors.front()) != closed_set.end()){
                                        if(pathReconstructMap.find(neighbors.front()) != pathReconstructMap.end()){
                                                if(temp_g_score >= pathReconstructMap[neighbors.front()].second){
                                                        neighbors.pop();
                                                        continue;
                                                }
                                        }
                                        visited = true;
                                }
                                
                                bool inRankMap = false;
                                for(it_rankMap1 = rankMap.begin(); it_rankMap1 != rankMap.end(); it_rankMap1++)
                                        if((*it_rankMap1).second == neighbors.front())
                                                break;
                                if(it_rankMap1 != rankMap.end())
                                        inRankMap = true;
                                
                                if(inRankMap == true && visited == false && temp_g_score < pathReconstructMap[neighbors.front()].second){
                                        double distance = temp_g_score + computeDistance(neighbors.front(), end_pnt) + penArray[j];
                                        if(distance < (*it_rankMap1).first){
                                                pathReconstructMap[neighbors.front()] = make_pair(cur_pnt, temp_g_score);
                                                rankMap.erase(it_rankMap1);
                                                for(it_rankMap1 = rankMap.begin(); it_rankMap1 != rankMap.end(); it_rankMap1++){
                                                        if(distance <= (*it_rankMap1).first){
                                                                rankMap.insert(it_rankMap1, make_pair(distance, neighbors.front()));
                                                                break;
                                                        }
                                                }
                                        }
                                        
                                        neighbors.pop();
                                        j++;
                                        continue;
                                }
                                
                                if((inRankMap == false && visited == false) || (visited == true && temp_g_score < pathReconstructMap[neighbors.front()].second))
                                        pathReconstructMap[neighbors.front()] = make_pair(cur_pnt, temp_g_score);
                                
                                if(inRankMap == false){
                                        double distance = pathReconstructMap[neighbors.front()].second + computeDistance(neighbors.front(), end_pnt);
                                        for(it_rankMap1 = rankMap.begin(); it_rankMap1 != rankMap.end(); it_rankMap1++){
                                                if(distance <= (*it_rankMap1).first){
                                                        rankMap.insert(it_rankMap1, make_pair(distance, neighbors.front()));
                                                        break;
                                                }
                                        }
                                        if(it_rankMap1 == rankMap.end()){
                                                if(distance <= ori_distance * control_factor)
                                                        rankMap.insert(it_rankMap1, make_pair(distance, neighbors.front()));
                                        }
                                }
                                
                                neighbors.pop();
                                j++;
                        }
                        
                        vector<point>::iterator it_point;
                        for(it_point = closed_set.begin(); it_point != closed_set.end(); it_point++)
                                if(*it_point == cur_pnt)
                                        break;
                        if(it_point == closed_set.end())
                                closed_set.push_back(cur_pnt);
                        
                        for(it_rankMap1 = rankMap.begin(); it_rankMap1 != rankMap.end(); it_rankMap1++){
                                if((*it_rankMap1).second == cur_pnt && cur_f_score == (*it_rankMap1).first){
                                        rankMap.erase(it_rankMap1);
                                        break;
                                }
                        }
                        
                }
                
                if(routed == false){
                        for(it_set = edges.begin(); it_set != edges.end(); it_set++)
                                rst->edgeUtils[*it_set]++;
                        edges.clear();
                        
                        rst->nets[net_id].routed = false;
                        cnt_unrouted++;
                        break;
                }
        }
        
        if(!edges.empty()){
                rst->nets[net_id].finalRoute.numSegs = edges.size();
                rst->nets[net_id].finalRoute.segments = new segment[edges.size()];
                point p1, p2;
                it_set = edges.begin();
                for(i = 0; i < rst->nets[net_id].finalRoute.numSegs; i++){
                        if(getPoints2D(*it_set, p1, p2, rst) == 1)
                                cout << "Can't find edge id " << *it_set << endl;
                        rst->nets[net_id].finalRoute.segments[i].p1 = p1;
                        rst->nets[net_id].finalRoute.segments[i].p2 = p2;
                        it_set++;
                }
                
                tot_wl += edges.size();
                swap(rst->nets[net_id].edges, edges);
        }
        
        return tot_wl;
}


bool lessPins(const net &n1, const net &n2){
        return (n1.numPins < n2.numPins);
}


bool moreWeight(const net &n1, const net &n2){
        return (n1.weight > n2.weight);
}


const int tot_itr_cnt = 1;
void updateHistoryWeight(int itr_cnt, routingInst *rst){
        
        int i;
        set<int>::iterator it_set;
        for(i = 0; i < rst->numEdges; i++)
                if(rst->edgeUtils[i] < 0)
                        rst->edgeHistory[i] += 1.2;
        
        for(i = 0; i < rst->numNets; i++){
                rst->nets[i].weight = 0.0;
                for(it_set = rst->nets[i].edges.begin(); it_set != rst->nets[i].edges.end(); it_set++)
                        rst->nets[i].weight += (double)(rst->edgeCaps[*it_set] - rst->edgeUtils[*it_set]) 
                                / rst->edgeCaps[*it_set] * (1 + (double)(rst->edgeHistory[*it_set]) / itr_cnt);
        }
        
}


int partial_release(routingInst *rst){
        
        int i;
	for(i = 0; i < rst->numNets; i++)
	{
                if(rst->nets[i].routed == true){
                        delete [] rst->nets[i].finalRoute.segments;
                        rst->nets[i].edges.clear();
                }
	}
        
        return 1;
}


int solveRouting(routingInst *rst){
        
        int i, itr_cnt;
        long tot_of = 0;
        long tot_wl = 0;
        vector<net> tmp_set;
        
        /*
        //Sorting nets based on pin counts
        //for(i = 0; i < rst->numNets; i++)
        //tmp_set.push_back(rst->nets[i]);
        
        //sort(tmp_set.begin() , tmp_set.end(), lessPins);
        //for(i = 0; i < rst->numNets; i++)
        //rst->nets[i] = tmp_set[i];
        */
        
        tmp_set.clear();
        
        pinOrdering(rst);
        //pinOrderingMST(rst);
                
        clock_t start, end, start_tot, end_tot;
        start_tot = clock();
        
        cout << "Simulation Report........." << endl;
        cout << "Itr\t#unrouted\ttot_wl\ttot_of\tRuntime(1rd)" << endl; 
        double control_factor = 1.0;
        for(itr_cnt = 0; itr_cnt < tot_itr_cnt; itr_cnt++){
                start = clock();
                
                cout << itr_cnt << "\t";
                for(i = 0; i < rst->numEdges; i++)
                        rst->edgeUtils[i] = rst->edgeCaps[i];
                
                for(i = 0; i < rst->numNets; i++)
                        rst->nets[i].routed = false;
                
                tot_wl = 0;
                cnt_unrouted = 0;
                if(itr_cnt == -1){
                        for(i = 0; i < rst->numNets; i++){
                                //cout << "Routing net " << i << endl;
                                tot_wl += spSingleNet(i, rst);
                        }
                }
                else{       
                        for(i = 0; i < rst->numNets; i++){
                                if(i % 10000 == 0)
                                        cout << "Routing net " << rst->nets[i].id << "\t" << rst->nets[i].numPins << endl;
                                tot_wl += AStarRoutepick(i, control_factor + itr_cnt * 0.05, rst);
                                //tot_wl += LeeRoutepick(i, control_factor + itr_cnt * 0.5, rst);
                                //tot_wl += AStarStarRoutepick(i, control_factor + itr_cnt * 0.1, rst);
                        }
                }
                //cout << "Number of unrouted nets is " << cnt_unrouted << endl;
                cout << cnt_unrouted << "\t";
                
                tot_of = 0;
                for(i = 0; i < rst->numEdges; i++){
                        if(rst->edgeUtils[i] < 0)
                                tot_of += abs(rst->edgeUtils[i]);
                }
                
                //cout << "total wirelength is " << tot_wl << endl;
                //cout << "total overflow is " << tot_of << endl;
                cout << tot_wl << "\t";
                cout << tot_of << endl;
                /*
                cnt_unrouted = 0;
                for(i = 0; i < rst->numNets; i++){
                        if(rst->nets[i].routed == false){
                                //cout << "Routing net " << rst->nets[i].id << "\t" << rst->nets[i].numPins << endl;
                                tot_wl += AStarRoutepick(i, control_factor + (itr_cnt + 1) * 0.1, rst);
                                //tot_wl += AStarStarRoutepick(i, rst);
                        }
                }
                //cout << "Number of unrouted nets is " << cnt_unrouted << endl;
                cout << "\t" << cnt_unrouted << "\t";
                
                tot_of = 0;
                for(i = 0; i < rst->numEdges; i++){
                        if(rst->edgeUtils[i] < 0)
                                tot_of += abs(rst->edgeUtils[i]);
                }
                
                //cout << "total wirelength is " << tot_wl << endl;
                //cout << "total overflow is " << tot_of << endl;
                cout << tot_wl << "\t";
                cout << tot_of << endl;
                */
                
                cnt_unrouted = 0;
                for(i = 0; i < rst->numNets; i++){
                        if(rst->nets[i].routed == false){
                                //cout << "Routing net " << i << endl;
                                tot_wl += spSingleNet(i, rst);
                        }
                }
               
                //cout << "Number of unrouted nets is " << cnt_unrouted << endl;
                
                cout << "\t" << cnt_unrouted << "\t";
                
                tot_of = 0;
                for(i = 0; i < rst->numEdges; i++){
                        if(rst->edgeUtils[i] < 0)
                                tot_of += abs(rst->edgeUtils[i]);
                }
                
                //cout << "total wirelength is " << tot_wl << endl;
                //cout << "total overflow is " << tot_of << endl;
                cout << tot_wl << "\t";
                cout << tot_of << endl;
                
                //updating weights
                updateHistoryWeight(itr_cnt, rst);
                
                tmp_set.clear();
                for(i = 0; i < rst->numNets; i++)
                        tmp_set.push_back(rst->nets[i]);
                
                sort(tmp_set.begin() , tmp_set.end(), moreWeight);
                for(i = 0; i < rst->numNets; i++)
                        rst->nets[i] = tmp_set[i];
                
                if(itr_cnt < tot_itr_cnt - 1)
                        partial_release(rst);
                
                end = clock();
                //cout << "One round of routing time is " << (float)(end - start) / CLOCKS_PER_SEC << endl;
                cout << "\t\t\t\t\t" << (float)(end - start) / CLOCKS_PER_SEC << " s" << endl;
                //if((float)(end - start) / CLOCKS_PER_SEC > 900.0)
                //break;
        }
        
        end_tot = clock();
        cout << "Total routing time is " << (float)(end_tot - start_tot) / CLOCKS_PER_SEC << endl;
        
        return 1;
}


int writeOutput(const char *outRouteFile, routingInst *rst){
        
        int i, k;
        ofstream fout;
        fout.open(outRouteFile);
        if(!fout)
        {
                cout<<"Fail to open output file"<<endl;
                return 0;
        }
        
        cout << "Writing solution..." << endl;
        for(i = 0; i < rst->numNets; i++) // each net
        {
                fout << "n";
                stringstream ss;
                ss << rst->nets[i].id;
                fout << ss.str() << endl;
                for(k = 0; k < rst->nets[i].finalRoute.numSegs; k++){
                        fout << "(";
                        fout << rst->nets[i].finalRoute.segments[k].p1.x << ",";
                        fout << rst->nets[i].finalRoute.segments[k].p1.y << ")-(";
                        fout << rst->nets[i].finalRoute.segments[k].p2.x << ",";
                        fout << rst->nets[i].finalRoute.segments[k].p2.y << ")" << endl;
                }
                fout << "!" << endl;
        }
        
        return 1;
}


int release(routingInst *rst){
	int i;
        
	for(i = 0; i < rst->numNets; i++)
	{
                //for(j = 0; j < rst->nets[i].finalRoute.numSegs; j++)
                //delete [] rst->nets[i].finalRoute.segments[j].edges;
                
                delete [] rst->nets[i].finalRoute.segments;
                delete [] rst->nets[i].pins;
                rst->nets[i].edges.clear();
	}
	
        delete [] rst->nets;
	delete [] rst->edgeCaps;
	delete [] rst->edgeUtils;
        delete [] rst->edgeHistory;
        
        delete rst;
        return 1;
}
  

